import java.util.Scanner;

/**
 * @author yu
 * @date 2025年04月19日 16:46
 */
/*class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}*/

public class _02_LinkedList_05_19removeNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 新建一个虚拟头节点指向 head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        // 快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n + 1 个结点即可！！！
        for (int i = 0; i <= n; i++) { // 注意范围
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }

    // 根据数组创建链表
    public ListNode createLinkedList(int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // 打印链表
    public void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        _02_LinkedList_05_19removeNthFromEnd solution = new _02_LinkedList_05_19removeNthFromEnd();
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入链表节点的值，用空格分隔：");
        String input = scanner.nextLine();
        String[] valuesStr = input.split(" ");
        int[] values = new int[valuesStr.length];
        for (int i = 0; i < valuesStr.length; i++) {
            values[i] = Integer.parseInt(valuesStr[i]);
        }

        ListNode head = solution.createLinkedList(values);

        System.out.println("请输入要移除的倒数第几个节点：");
        int n = scanner.nextInt();

        System.out.println("原始链表：");
        solution.printLinkedList(head);

        ListNode newHead = solution.removeNthFromEnd(head, n);

        System.out.println("移除倒数第 " + n + " 个节点后的链表：");
        solution.printLinkedList(newHead);

        scanner.close();
    }
}